//给定一个二叉树，检查它是否是镜像对称的。 
//
// 
//
// 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 
//
//     1
//   / \
//  2   2
// / \ / \
//3  4 4  3
// 
//
// 
//
// 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 
//
//     1
//   / \
//  2   2
//   \   \
//   3    3
// 
//
// 
//
// 进阶： 
//
// 你可以运用递归和迭代两种方法解决这个问题吗？ 
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 1669 👎 0

package leetcode.editor.cn;
//leetcode submit region begin(Prohibit modification and deletion)

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution101 {
    /**
     * 使用栈
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        if(root == null) return true;
        stack.push(root.right);
        stack.push(root.left);
        while(!stack.isEmpty()){
            TreeNode left = stack.pop();
            TreeNode right = stack.pop();
            //这里不能直接返回，因为队列中可能还有元素
            //if(left == null && right == null) return true;
            if(left == null && right == null) continue;
            if(left == null || right == null) return false;
            if(left.val != right.val) return false;
            stack.push(left.left);
            stack.push(right.right);
            stack.push(left.right);
            stack.push(right.left);
        }
        return true;
    }

    /**
     * 迭代，使用队列
     */
    public boolean isSymmetric2(TreeNode root) {
        if(root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while(!queue.isEmpty()){
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            //这里写法太复杂了
//            if(left == null && right != null) return false;
//            if(left != null && right == null) return false;
//            if(left != null){
//                if(left.val != right.val){
//                    return false;
//                }
//                queue.offer(left.left);
//                queue.offer(right.right);
//                queue.offer(left.right);
//                queue.offer(right.left);
//            }
            if(left == null && right == null){
                continue;
            }
            if(left == null || right == null || left.val!=right.val){
                return false;
            }
            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(left.right);
            queue.offer(right.left);
        }
        return true;
    }

    /**
     * 递归
     */
    public boolean isSymmetric1(TreeNode root) {
        if(root == null){
            return true;
        }
        return symmetric(root.left,root.right);
    }

    public boolean symmetric(TreeNode left, TreeNode right){
        if(left == null && right == null){
            return true;
        }
        if(left == null || right == null){
            return false;
        }
        return left.val == right.val && symmetric(left.left,right.right) && symmetric(left.right,right.left);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
